package com.zjj.lbw.interview.tree;

import com.zjj.lbw.interview.common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhanglei.zjj
 * @description 二叉树后序遍历
 * @date 2023/9/3 12:07
 */
public class BinaryTreePostOrder {
    /**
     * 二叉树后序遍历-递归
     *
     * @param root
     */
    public static void postorderRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderRecursion(root.left);
        postorderRecursion(root.right);
        System.out.println(root.val);
    }

    /**
     * 二叉树后序遍历-迭代
     *
     * @param root
     */
    public static void postorderIteration(TreeNode root) {
        if (root != null) {
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode prev = null;
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }

                TreeNode headNode = stack.pop();
                // 后序遍历栈顶元素不一能就能立马打印，还要看有没有右子节点
                // 如果遍历到某个节点时，恰好它的上一次打印节点是它的右子节点，说明它的右子树已经处理完
                // 这个节点必然是第二次遍历到它，可以打印了
                if (headNode.right == null || headNode.right == prev) {
                    System.out.println(headNode.val);

                    // 打印过的元素做个标记
                    prev = headNode;

                } else {
                    // 右子节点有值，还不能遍历，重新入栈
                    stack.push(headNode);
                    root = headNode.right;
                }
            }
        }
    }

    /**
     * 二叉树后序遍历-morris遍历
     * @param root
     */
    public static void postorderMorris(TreeNode root) {
        TreeNode originNode = root;
        if (root == null) {
            return;
        }
        TreeNode mostRight = null;
        while (root != null) {
            mostRight = root.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != root) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = root;
                    root = root.left;
                    continue;
                } else {
                    mostRight.right = null;
                    // 要么当前节点的前驱节点是它的左子节点（只有一个节点），要么当前节点的前驱节点在一个链表中
                    // 链表的统一节点是当前节点左节点，链表的尾节点就是当前节点的前驱节点
                    // 这两种情况都可以看作是遍历打印当前节点左子节点这个链表（需要反转遍历打印）
                    printNode(root.left);
                }
            }
            root = root.right;

        }

        // 根节点，右子树链表 不属于上面的情况，需要单独遍历打印
        printNode(originNode);

    }

    /**
     * 打印单链表（需要先反转-打印-再反转还原）
     * @param node
     */
    private static void printNode(TreeNode node) {
        if (node == null) {
            return;
        }
        // 链表反转
        TreeNode tail = transferChain(node);
        // 打印
        TreeNode cur = tail;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.right;
        }
        // 为了保证之前的树形结构不变，需要再次反转还原
        transferChain(tail);

    }

    private static TreeNode transferChain(TreeNode node) {
        TreeNode prev = null, cur, next;
        cur = node;
        while (cur != null) {
            next = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }


    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        postorderRecursion(node1);
//        postorderIteration(node1);
        postorderMorris(node1);
    }
}
